package com.wenhai.mj.tree;

public class AVLTree<E> extends BinarySearchTree<E> {


    private static class AVLNode<E> extends Node<E> {
        int height = 1;

        AVLNode(Node<E> parent, E element) {
            super(parent, element);
        }

        int balanceFactor() {
            int rightHeight = this.right == null ? 0 : ((AVLNode) right).height;
            int leftHeight  = this.left == null ? 0 : ((AVLNode) left).height;
            return leftHeight - rightHeight;
        }

        boolean isBalance() {
            return Math.abs(balanceFactor()) <= 1;
        }

        void updateHeight() {
            int rightHeight = this.right == null ? 0 : ((AVLNode) right).height;
            int leftHeight  = this.left == null ? 0 : ((AVLNode) left).height;
            this.height     = 1 + Math.max(rightHeight, leftHeight);
        }

        boolean isRightLeaf() {
            return this.parent != null && this.right == parent.right;
        }

        boolean isLeftLeaf() {
            return this.parent != null && this.left == parent.left;
        }

        Node<E> tallerNode() {
            int rightHeight = this.right == null ? 0 : ((AVLNode) right).height;
            int leftHeight  = this.left == null ? 0 : ((AVLNode) left).height;
            if (rightHeight > leftHeight) {
                return this.right;
            } else if (rightHeight < leftHeight) {
                return this.left;
            } else {
                return this.isLeftLeaf() ? this.left : this.right;
            }
        }

        void rotateRight() {

        }

        void rotateLeft() {

        }

        void rebalance() {
            AVLNode<E> parentNode = (AVLNode<E>)this.tallerNode();
            AVLNode<E> node       = (AVLNode<E>) parentNode.tallerNode();
            if (parentNode.isLeftLeaf()) {
                if (node.isLeftLeaf()) { // LL
                    this.rotateRight();
                } else { // LR
                    parentNode.rotateLeft();
                    this.rotateRight();
                }
            } else {
                if (node.isRightLeaf()) { //RR
                    this.rotateLeft();
                } else {    // RL
                    parentNode.rotateRight();
                    this.rotateLeft();
                }
            }
        }

    }

    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (((AVLNode) node).isBalance()) {
                // 更新高度
                ((AVLNode<E>) node).updateHeight();
            } else {
                // 使其平衡
                ((AVLNode<E>) node).rebalance();
                break;
            }
        }
    }

    @Override
    protected Node<E> createNode(Node<E> parent, E element) {
        return new AVLNode<>(parent, element);
    }

}
